#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
       //dp[i]代表以i位置为结尾的子数组中，最大的和为多少
       //然后就是状态转移方程了
       //dp[i] = max(dp[i-1]+nums[i],nums[i])
       //初始化，全部初始化为0
       //填表顺序从左到右
       //返回值dp表中的最大值
       int ret = -0x7f7f7f;
       int n = nums.size();
       int dp[100001] = {0};
       for(int i = 1;i<=n;i++)
       {
            dp[i] = max(dp[i-1]+nums[i-1],nums[i-1]);
            ret = max(ret,dp[i]);
       }
       return ret;
    }
};